// https://leetcode.cn/problems/duplicate-zeros/
// Created by ade on 2022/10/31.
//

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int l = 0, r = n - 1;
        while(l < r){
            if(arr[l] != 0){
                l++;
                continue;
            }
            l++;
            r--;
        }
        if(r == n - 1) return;
        int diff = n - r - 1, i = 0;
        if(l == r && arr[l] == 0) diff++; // 临界条件的判断非常重要，该条件下，是少算一次0的
        if(r + 1 + diff > n && arr[r] == 0){
            // 如果刚好最后一次是0的情况下，需要判断最后一个0是否需要被复制
            arr[n - 1 - i] = 0;
            r--;
            diff--;
            i++;
        }
        while(diff > 0) {
            arr[n - 1 - i] = arr[r];
            i++;
            if(arr[r] != 0){
                r--;
                continue;
            }
            arr[n - 1 - i] = 0;
            diff--;
            r--;
            i++;
        }
    }
};